#include <vector>
#include <set>
using namespace std;
struct node
{
    // 自定义去重机制
    bool operator<(const node &n) const
    {
        return end < n.start;
    }
    node(const vector<int> &vt) : start(vt[0]), end(vt[1]) { ; }
    int start;
    int end;
};
class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        set<node> st;
        for (auto &vt : intervals)
        {
            node cur_node(vt);
            // 合并相同区间
            for (auto it = st.find(cur_node); it != st.end(); it = st.find(cur_node))
            {
                cur_node.start = min(cur_node.start, it->start);
                cur_node.end = max(cur_node.end, it->end);
                st.erase(it);
            }
            // 插入
            st.insert(std::move(cur_node));
        }
        vector<vector<int>> res;
        for (auto it = st.begin(); it != st.end(); it++)
        {
            res.push_back({it->start, it->end});
        }
        return res;
    }
};
#include <algorithm>
// 排序方法
class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        // 排序
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res{intervals.front()};
        // 插入或者修正每一个重合区间的长度
        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i][0] <= res.back()[1])
                res.back()[1] = max(intervals[i][1], res.back()[1]);
            else
                res.push_back(intervals[i]);
        }
        return res;
    }
};